package com.demo.java.OD301_350.OD333;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【跳房子2(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146150188
 */
public class OdMain {
    private static int minIndexSum = Integer.MAX_VALUE;  // 存储当前最小的索引和
    private static int targetCount;  // 存储目标和
    private static List<Integer> result;  // 存储最终的结果组合

    public static void main(String[] args) {
        // 读取输入
        Scanner scanner = new Scanner(System.in);
        targetCount = Integer.parseInt(scanner.nextLine());  // 读取目标和
        String[] stringArray = scanner.nextLine().replaceAll("[\\[\\]]", "").split(",");  // 读取数字数组
        int[] nums = new int[stringArray.length];  // 初始化数组存储数字
        for (int i = 0; i < stringArray.length; i++) {
            nums[i] = Integer.parseInt(stringArray[i]);  // 填充数字数组
        }

        // 调用回溯算法求解
        dfs(nums, 3, new ArrayList<>(), new ArrayList<>(), 0);

        // 构造并输出最终的结果
        StringBuilder output = new StringBuilder("[");
        for (int i = 0; i < result.size(); i++) {
            output.append(result.get(i));  // 将结果组合输出
            if (i != result.size() - 1) {
                output.append(",");
            }
        }
        output.append("]");
        System.out.println(output.toString());  // 打印最终结果
        scanner.close();  // 关闭扫描器
    }

    // 回溯法：生成所有可能的三元组合
    private static void dfs(int[] nums, int remaining, List<Integer> combination,
                            List<Integer> indices, int index) {
        if (remaining == 0) {  // 当剩余选择为0时，判断当前组合是否符合条件
            int total = 0;  // 当前组合的总和
            int indexSumTemp = 0;  // 当前组合的索引和
            for (int i = 0; i < 3; i++) {  // 遍历当前组合
                total += combination.get(i);  // 计算组合的总和
                indexSumTemp += indices.get(i);  // 计算组合的索引和
            }
            if (total == targetCount && indexSumTemp < minIndexSum) {  // 满足条件时更新结果
                minIndexSum = indexSumTemp;  // 更新最小索引和
                result = new ArrayList<>(combination);  // 更新最优组合
            }
        } else {
            // 遍历所有剩余的元素，递归选择
            for (int i = index; i < nums.length; i++) {
                combination.add(nums[i]);  // 选择当前元素
                indices.add(i);  // 记录当前元素的索引
                dfs(nums, remaining - 1, combination, indices, i + 1);  // 递归调用
                combination.remove(combination.size() - 1);  // 回溯，移除最后一个元素
                indices.remove(indices.size() - 1);  // 回溯，移除最后一个索引
            }
        }
    }
}